n = 250250
d = 250

mod = 10 ** 16

a = [ pow(i, i, d) for i in xrange(1, n + 1)]
count0 = a.count(0)
a = [num for num in a if num != 0]
print a.count(0)
dp = [0 for i in xrange(d + d)]

dp[0] = pow(2, count0, mod)

total = len(a)
it = 0
for num in a:
    for i in xrange(d-1, -1, -1):
        dp[i + num] += dp[i]
    for i in xrange(d, d + d):
        dp[i-d] += dp[i]
        dp[i] = 0
        if dp[i-d] > mod:
            dp[i-d] %= mod
    it += 1
    if it % 1000 == 0:
        print 100.0 * it / total

print dp[0] - 1
print dp

